import java.util.*;

public class Solution279 {
    class BfsEle{
        int step;
        int sum;
        BfsEle(int step,int sum){
            this.step=step;
            this.sum=sum;
        }
    }

    List<Integer> getPowNums(int n){
        List<Integer> res=new ArrayList<>();
        int num=1;
        while(true){
            int tmpPowNum=num*num;
            if(tmpPowNum>n){
                break;
            }
            res.add(tmpPowNum);
            num++;
        }
        Collections.reverse(res);
        return res;
    }


    public int numSquares(int n) {
        var powNums=getPowNums(n);
        Queue<BfsEle> queue=new LinkedList<>();
        Set<Integer> memory=new HashSet<>();
        queue.add(new BfsEle(0,0));
        while(!queue.isEmpty()){
            BfsEle tmpTop=queue.poll();
            int tmpSum=tmpTop.sum;
            int tmpStep=tmpTop.step;
            if(memory.contains(tmpSum)){
                continue;
            }
            if(tmpSum==n){
                return tmpStep;
            }
            memory.add(tmpSum);
            for (Integer PowNum:powNums) {
                int addNum=tmpSum+PowNum;
                if(addNum<=n)
                queue.add(new BfsEle(tmpStep+1,addNum));
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution279 s=new Solution279();
        System.out.println(s.numSquares(7168));
    }
}
